package offer2

/**
原题链接：
https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

B站 帅地玩编程
剑指offer 51.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

输入描述:
题目保证输入的数组中没有的相同的数字

示例 1:
输入: [7,5,6,4]
输出: 5
*/

func reversePairs(record []int) int {

	if len(record) <= 1 {
		return 0
	} // 特殊判断，数组长度<=1，直接返回0

	return mergeSort(record, 0, len(record)-1) // 归并排序，统计逆序对个数
}

// 归并排序
func mergeSort(nums []int, left int, right int) int {
	if left >= right {
		return 0
	}

	mid := (right-left)/2 + left
	x1 := mergeSort(nums, left, mid)
	x2 := mergeSort(nums, mid+1, right)
	x3 := merge(nums, left, mid, mid+1, right)

	return x1 + x2 + x3
}

func merge(nums []int, l1 int, r1 int, l2 int, r2 int) int {

	temp := make([]int, r2-l1+1) // 创建临时数组，存储排序好的元素

	count := 0 // 声明逆序对计数

	i := l1 // 声明左右指针，分别从左右子数组的左下标开始
	j := l2
	k := 0 // 临时数组的下标

	for i <= r1 && j <= r2 { // 只要左右指针没有超过范围，持续遍历
		if nums[i] > nums[j] { // 如果左[i] > 右[j]，那么可以构成 (l2-i) 个逆序对
			count += l2 - i
			temp[k] = nums[j] // 向临时数组中添加排序好的元素
			j++
		} else {
			temp[k] = nums[i] // 向临时数组中添加排序好的元素
			i++
		}
		k++
	}

	for i <= r1 { // 一旦左右数组其中一个已经遍历完毕，将另一个数组中的元素直接复制到临时数组中
		temp[k] = nums[i]
		i++
		k++
	}
	for j <= r2 {
		temp[k] = nums[j]
		j++
		k++
	}

	k = 0 // 把临时数组复制回原数组
	for i := l1; i <= r2; i++ {
		nums[i] = temp[k]
		k++
	}

	return count // 返回计数
}
